package com.Oct_Twenty;

/**
 * 779. 第K个语法符号
 * 我们构建了一个包含 n 行( 索引从 1  开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
 *
 * 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
 * 给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/k-th-symbol-in-grammar
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/20 23:25
 */

public class Solution779 {

    public int kthGrammar(int n, int k) {
        if (n==1&&k==1) return 0;
        int a=kthGrammar(n-1,(k+1)/2);
        int b=-(a-1);
        if (k%2==1)
        {
            return a;
        }else
        {
            return b;
        }
    }

    public static void main(String[] args) {
        Solution779 solution779=new Solution779();
        System.out.println(solution779.kthGrammar(3,2));
    }

}
